/**
 *  @file BinTree.cpp
 */
#include "../../common/CppMemPool.h"
#include "BinTree.h"
#include "TreeNode.h"
#include "../ArrayT.h"

namespace cppflib
{

namespace collections
{

namespace tree
{

/**
 *  @param [in] isReplacedWithPredecessor -- when deleing a node with 2 children whether it should be replaced
 *                                           by predecessor or successor
 */
BinTree::BinTree(bool isReplacedWithPredecessor)
{
   m_pRootNode = NULL;
   m_nodeCount = 0;
   m_treeWalkCB = NULL;
   m_isReplacedWithPredecessor = isReplacedWithPredecessor;
}

BinTree::BinTree(void)
{
   m_pRootNode = NULL;
   m_nodeCount = 0;
   m_treeWalkCB = NULL;
   m_isReplacedWithPredecessor = false;
}

BinTree::~BinTree(void)
{
   FreeTree();
   
   if (m_treeWalkCB)
      cppmempool::Release(m_treeWalkCB);
}

/**
 *   Test if tree is empty
 *
 *   @return true -- tree is empty
 *   @return false -- tree is NOT empty
 */
bool BinTree::IsTreeEmpty(void)
{
    return (m_pRootNode == NULL || m_nodeCount == 0);
}

/**
 *  Get number of nodes in this tree
 */
u32_t BinTree::GetCount(void)
{
    return m_nodeCount;
}

/**
 *  Get root node (may be NULL)
 */
TreeNode * BinTree::GetRootNode(void)
{
    return m_pRootNode;
}

/**
 *  Set the callback function for tree walking
 */
void BinTree::SetTreeWalkCallback(const TreeWalkCallback &treeWalkCB)
{
    if (m_treeWalkCB)
       cppmempool::Release(m_treeWalkCB);
    
    m_treeWalkCB = new TreeWalkCallback(treeWalkCB);
    cppmempool::Retain(m_treeWalkCB);
}

/**
 *  Traverse all tree node in a breath-first manner.
 */
void BinTree::BreathFirstTraverse(TreeNode * pNode)
{
    if (IsTreeEmpty())
       return;
    
    ArrayCppObjT<TreeNode> nodeArray(m_nodeCount);  // use an array to chain up all nodes in the breath first order
    int start = 0, end = 1;
    
    if (!pNode)
       pNode = m_pRootNode;

    // chain up the nodes
    nodeArray.Set(start, pNode);
    while (end < static_cast<int>(m_nodeCount)) {
       TreeNode *pTemp = nodeArray.Get(start++);
       
       if (pTemp->m_leftChild) 
          nodeArray.Set(end++, pTemp->m_leftChild);

       if (pTemp->m_rightChild) 
          nodeArray.Set(end++, pTemp->m_rightChild);
    }

    // Print all elements now
    for (int i = 0; i < static_cast<int>(nodeArray.GetSize()); ++i) {
       if (m_treeWalkCB) (*m_treeWalkCB)(nodeArray.Get(i));
    }

}

/**
 *  Inorder walk from root
 */
void BinTree::InorderWalk(void)
{
   InorderWalk(m_pRootNode);
}

/**
 *  Walk tree by INORDER 
 *
 *  @param [in] pNode -- must be a pointer to one of the node inside this tree
 */
void BinTree::InorderWalk(TreeNode * pNode)
{
   if (pNode != NULL) {
      InorderWalk(pNode->m_leftChild);
      if (m_treeWalkCB) (*m_treeWalkCB)(pNode);
      InorderWalk(pNode->m_rightChild);
   }
}

/**
 *  Preorder walk from root
 */
void BinTree::PreorderWalk(void)
{
   PreorderWalk(m_pRootNode);
}

/**
 *  Walk tree by PREORDER
 *
 *  @param [in] pNode -- must be a pointer to one of the node inside this tree
 */
void BinTree::PreorderWalk(TreeNode * pNode)
{
   if (pNode != NULL) {
      if (m_treeWalkCB) (*m_treeWalkCB)(pNode);
      PreorderWalk(pNode->m_leftChild);      
      PreorderWalk(pNode->m_rightChild);
   }
}

/**
 *  Postorder walk from root
 */
void BinTree::PostorderWalk(void)
{
   PostorderWalk(m_pRootNode);
}

/**
 *  Walk tree by POSTORDER
 *
 *  @param [in] pNode -- must be a pointer to one of the node inside this tree
 */
void BinTree::PostorderWalk(TreeNode * pNode)
{
   if (pNode != NULL) {      
      PostorderWalk(pNode->m_leftChild);      
      PostorderWalk(pNode->m_rightChild);
      if (m_treeWalkCB) (*m_treeWalkCB)(pNode);
   }
}

/**
 *  Get node with "smallest" key
 *
 *  @param [in] pNode -- the tree to be traversed rooted at pNode. 
 *                       NULL to search from root.
 *
 *  @note pNode MUST be a node in this tree
 *
 *  @return pointer to node with "smallest" key
 */
TreeNode * BinTree::GetMin(TreeNode * pNode)
{
    TreeNode * pTraNode = pNode ? pNode : m_pRootNode;

    if (pTraNode) {
       while (pTraNode->m_leftChild != NULL)
           pTraNode = pTraNode->m_leftChild;
    }

    return pTraNode;
}

/**
 *  Get node with "greatest" key
 * 
 *  @param [in] pNode -- the tree to be traversed rooted at pNode. 
 *                       NULL to search at root.
 *
 *  @note pNode MUST be a node in this tree
 *
 *  @return pointer to node with "greatest" key
 */
TreeNode * BinTree::GetMax(TreeNode * pNode)
{
    TreeNode * pTraNode = pNode ? pNode : m_pRootNode;

    if (pTraNode) {
       while (pTraNode->m_rightChild != NULL)
           pTraNode = pTraNode->m_rightChild;
    }

    return pTraNode;
}

/**
 *  Get the successor of a node
 *
 *  @param [in] pNode -- the node that its successor is to be retrieved
 *
 *  @note pNode MUST be a node in this tree
 *
 *  @return pointer to the node's successor (may be NULL)
 */
TreeNode * BinTree::GetSuccessor(TreeNode * pNode)
{
    if (!pNode)
       return NULL;

    if (pNode->m_rightChild != NULL)
       return GetMin(pNode->m_rightChild);

    TreeNode * pTemp = pNode->m_pParent;

    while(pTemp != NULL && pNode == pTemp->m_rightChild) {
       pNode = pTemp;
       pTemp = pTemp->m_pParent;
    }

    return pTemp;
}

/**
 *  Get the predecessor of a node
 *
 *  @param [in] pNode -- the node that its predecessor is to be retrieved
 *
 *  @note pNode MUST be a node in this tree
 *
 *  @return pointer to the node's predecessor (may be NULL)
 */
TreeNode * BinTree::GetPredecessor(TreeNode * pNode)
{
    if (!pNode)
       return NULL;

    if (pNode->m_leftChild != NULL)
       return GetMax(pNode->m_leftChild);

    TreeNode * pTemp = pNode->m_pParent;

    while(pTemp != NULL && pNode == pTemp->m_leftChild) {
       pNode = pTemp;
       pTemp = pTemp->m_pParent;
    }

    return pTemp;

}


/**
 *  Perform a right rotate at pNode
 *
 *  pNode is 'c' here:
 *             
 *        c            a
 *       / \          / \
 *      a   e   -->  b   c
 *     / \              / \
 *    b  d             d   e
 *      
 *
 *  @note pNode MUST be a node in this tree
 */
void BinTree::RightRotate(TreeNode * pNode)
{
   if (!pNode)
      return;

   TreeNode *pLeftChild = pNode->m_leftChild;
   TreeNode *pParent = pNode->m_pParent;

   // no left child, no rotation
   if (!pLeftChild) 
      return;

   // c's parent and a
   if (pParent) {
      pLeftChild->m_pParent = pParent;
      if (pParent->m_rightChild == pNode) 
         pParent->m_rightChild = pLeftChild;
      else 
         pParent->m_leftChild = pLeftChild;
   }
   else {
      // this tree points to a new root
      pLeftChild->m_pParent = NULL;
      this->m_pRootNode = pLeftChild;
   }

   // c and d (d may be null)
   pNode->m_leftChild = pLeftChild->m_rightChild;
   if (pNode->m_leftChild) pNode->m_leftChild->m_pParent = pNode;

   // c and a
   pNode->m_pParent = pLeftChild;
   pLeftChild->m_rightChild = pNode;

}

/**
 *  Perform a left rotate at pNode
 *
 *  pNode is 'a' here:
 *             
 *        a            c            
 *       / \          / \
 *      b   c  -->   a   e     
 *         / \      / \
 *        d   e    b   d            
 *      
 *
 *
 *  @note pNode MUST be a node in this tree
 */
void BinTree::LeftRotate(TreeNode * pNode)
{
   if (!pNode)
      return;

   TreeNode *pParent = pNode->m_pParent;
   TreeNode *pRightChild = pNode->m_rightChild;
   
   // no right child, no rotation
   if (!pRightChild) 
      return;

   // a's parent and c
   if (pParent) {
      pRightChild->m_pParent = pParent;
      if (pParent->m_rightChild == pNode) 
         pParent->m_rightChild = pRightChild;
      else 
         pParent->m_leftChild = pRightChild;
   }
   else {
      // this tree points to a new root
      pRightChild->m_pParent = NULL;
      this->m_pRootNode = pRightChild;
   }

   // a and d (d may be null)
   pNode->m_rightChild = pRightChild->m_leftChild;
   if (pNode->m_rightChild) pNode->m_rightChild->m_pParent = pNode;

   // a and c
   pNode->m_pParent = pRightChild;
   pRightChild->m_leftChild = pNode;
}



/**
 *  Search a node in this tree with the same key as the node passed in.
 *
 *  @param [in] node -- the node with a key to be searched
 *
 *  @note node is NOT a node in this tree
 *  
 *  @return pointer to the node found. NULL if not found.
 */
TreeNode * BinTree::Search(const TreeNode &node) const
{
    TreeNode * pTraNode = m_pRootNode;
    int cmpRet;

    while (pTraNode != NULL) {
       cmpRet = pTraNode->Compare(node);
       if (cmpRet == 0)
          break;
       else if (cmpRet > 0)
          pTraNode = pTraNode->m_leftChild;
       else
          pTraNode = pTraNode->m_rightChild;       
    }

    return pTraNode;
}

/**
 *  Insert a node in this tree.
 *
 *  @param [in] pNode -- A new node to be inserted
 *
 *  @return true -- node is inserted
 *  @return false -- node insertion failed
 */
bool BinTree::Insert(TreeNode *pNode)
{
    if (!pNode)
       return false;

    TreeNode * pTraNode = m_pRootNode;

    cppmempool::Retain(pNode);

    ++m_nodeCount;

    if (pTraNode == NULL) {
       m_pRootNode = pNode;
    }
    else {
       TreeNode * pParent = NULL;
       
       // traverse down the tree
       while(pTraNode) {
          pParent = pTraNode;
          
          if (pTraNode->Compare(*pNode) > 0)
             pTraNode = pTraNode->m_leftChild;
          else 
             pTraNode = pTraNode->m_rightChild;
       }

       // insert to tree
       pNode->m_pParent = pParent;       // assign parent

       if (pParent->Compare(*pNode) > 0)  
          pParent->m_leftChild = pNode;  // assign left child
       else
          pParent->m_rightChild = pNode; // assign right child
    }


    return true;
}

/**
 *  Delete a node from this tree
 *
 *  @param [in] node -- the node with the key to be deleted
 *
 *  @note node is NOT a node in this tree
 *
 *  @return true -- node is found and deleted
 *  @return false -- node is NOT found.
 */
bool BinTree::Delete(const TreeNode &node)
{
    TreeNode* pDelParent = NULL; // not used
    bool isLeftChild = false;    // not used

    return Delete(node, pDelParent, isLeftChild);
}

/**
 *  Delete node and return more information on return
 *
 *  @note node is NOT a node in this tree
 *
 *  @param [out] pDelParent -- deleted node's parent
 *  @param [out] isLeftChild -- true: pDelParent's left child is deleted,
 *                              false: pDelParent's right child is deleted.
 */
bool BinTree::Delete(const TreeNode &node, TreeNode* &pDelParent, bool & isLeftChild)
{
    TreeNode * pDelNode = Search(node);

    if (!pDelNode)
       return false;

    
    TreeNode * pParent;

    // case I: no children
    if (pDelNode->m_leftChild == NULL && pDelNode->m_rightChild == NULL) {
       pParent = pDelNode->m_pParent;
       pDelParent = pParent;  // return to caller

       if (pParent) {
          if (pParent->m_leftChild == pDelNode) {
             pParent->m_leftChild = NULL;
             isLeftChild = true;
          }
          else {
             pParent->m_rightChild = NULL;
             isLeftChild = false;
          }
       }
       else {
          m_pRootNode = NULL;
       }
       
    }
    // case II: only left child present
    else if (pDelNode->m_leftChild != NULL && pDelNode->m_rightChild == NULL) {
       TreeNode * pChildNode = pDelNode->m_leftChild;
       pParent = pDelNode->m_pParent;
       pDelParent = pParent;  // return to caller

       if (pParent) {
          
          if (pParent->m_leftChild == pDelNode) {  // assign child
             pParent->m_leftChild = pChildNode;
             isLeftChild = true;
          }
          else {
             pParent->m_rightChild = pChildNode;
             isLeftChild = false;
          }
          
          pChildNode->m_pParent = pParent;    // assign parent
       }
       else {
          m_pRootNode = pChildNode;
          pChildNode->m_pParent = NULL;  // assign parent to NULL
       }

    }
    // case III: only right child present
    else if (pDelNode->m_leftChild == NULL && pDelNode->m_rightChild != NULL) {
       TreeNode * pChildNode = pDelNode->m_rightChild;
       pParent = pDelNode->m_pParent;
       pDelParent = pParent;  // return to caller

       if (pParent) {
          if (pParent->m_leftChild == pDelNode) {   // assign child
             pParent->m_leftChild = pChildNode;
             isLeftChild = true;
          }
          else {
             pParent->m_rightChild = pChildNode;
             isLeftChild = false;
          }
          
          pChildNode->m_pParent = pParent;      // assign parent
       }
       else {
          m_pRootNode = pChildNode;
          pChildNode->m_pParent = NULL;    // assign parent to NULL
       }

    }
    // case IV: both children are present
    else {
       // get predecessor or successor node for replacement
       TreeNode * pReplacingNode = m_isReplacedWithPredecessor ? GetPredecessor(pDelNode) : GetSuccessor(pDelNode);
       // predecessor or successor node will have at most one child.
       TreeNode * pChildNode = pReplacingNode->m_leftChild ? pReplacingNode->m_leftChild : pReplacingNode->m_rightChild;
       
       pParent = pReplacingNode->m_pParent;  
       pDelParent = pParent;  // return to caller
     
       if (pParent->m_leftChild == pReplacingNode) {
          pParent->m_leftChild = pChildNode;    // may be NULL
          isLeftChild = true;
       }
       else {
          pParent->m_rightChild = pChildNode;   // may be NULL
          isLeftChild = false;
       }

       if (pChildNode)
          pChildNode->m_pParent = pParent;    // assign parent
       
       // copy content from its successor
       pDelNode->CopyFromNode(*pReplacingNode);
       
       // we delete the successor instead
       pDelNode = pReplacingNode;
    }

    cppmempool::Release(pDelNode);
    --m_nodeCount;
     
    return true;  
}

/**
 *  Free the tree
 */
void BinTree::FreeTree(void)
{
    if (!IsTreeEmpty()) {
       FreeByPostorder(m_pRootNode);
       m_pRootNode = NULL;
    }
}

/**
 *  Free tree in post order
 *
 *  @note pNode MUST be a node in this tree
 */
void BinTree::FreeByPostorder(TreeNode * pNode)
{
    if (pNode != NULL) {
       FreeByPostorder(pNode->m_leftChild);
       FreeByPostorder(pNode->m_rightChild);
       cppmempool::Release(pNode);
       --m_nodeCount;
    }
}


}  // end of namespace tree

}  // end of namespace collections

}  // end of namespace cppflib

